\documentclass[a4paper, 11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[frenchb]{babel} 
\usepackage{geometry}
\usepackage{graphicx}

\usepackage{algorithm2e}
\SetKwIF{If}{Elseif}{Else}{Si}{alors}{Sinon si}{Sinon}{Sin si}
\SetKwFor{For}{Pour}{faire}{Fin pour}
\SetKwFor{While}{Tant que}{faire}{Fin tant que}
\SetKwInput{KwData}{Données}
\SetKwInput{KwResult}{Résultat}
\SetKwBlock{Begin}{Début}{Fin}
\SetKw{KwTo}{à}

\geometry{hmargin=3cm,vmargin=3.5cm}



\title{ \textbf{GLIN601 :} Projet Gestion des Préférences\\Compte rendu du 19 mars 2013}
\author{AMMAR Ines, CARBONNEL Jessie et LY Julie}

\begin{document}
	\maketitle
	
	\renewcommand{\contentsname}{}
	\setcounter{tocdepth}{2}


\section{Classes}
\subsection{Recherches}
Après avoir analysé les différentes notions importantes à la réalisation de calculs de préférences (variable, instanciation, ensemble d'alternatives combinatoires, préférence et contrainte), nous avons établi les différents attributs et méthodes dont nous pourrions avoir besoins pour utiliser ces classes.
\subsubsection{Variable}
\textbf{Attributs}\\
 - Une variable va posséder un nom sous forme de chaine de caractères.\\
 - Elle va aussi posséder un domaine représenté par une collection de valeurs.\\
. Nous ne ferons pas de classe "Valeur" : elles seront simplement représentées par des chaines de caractères.\\
. Chaque valeur doit avoir un nom unique !\\

\textbf{Méthodes}\\
 - Récupérer le nom et le domaine.\\
 - Ajouter / enlever une valeur du domaine.\\
 - Récupérer le nombre de valeurs du domaine.

\subsubsection{Outcome}
\textbf{Attributs}\\
 - Une instanciation doit contenir une collection de valeurs.\\

\textbf{Méthodes}\\
 - Récupérer l'ensemble des valeurs.\\
 - Récupérer le nombre de valeurs.\\
 - Vérifier si une valeurs est dans l'ensemble.\\
 - Comparer deux Outcomes.

\subsubsection{Omega}
\textbf{Attributs}\\
 - Pour la définition par intention : l'ensemble des variables sur lesquelles Omega est fondé.\\
 - Pour la définition par extension : une collection d'Outcomes.\\
. La collection d'Outcomes est vide dans un premier temps : on l'a générera lorsque l'on en aura besoin (explosion combinatoire).\\
. Il ne doit pas y avoir deux Outcomes identiques dans Oméga.\\

\textbf{Méthodes}\\
 - Récupérer l'ensemble des Variables.\\
 - Récupérer la taille maximale de Omega.\\
 - Récupérer la taille actuelle de Omega (lorsque l'on aura retiré des Outcomes).\\
 - Enlever une Outcome.\\
 - Générer l'ensemble d'Outcomes à partir de l'ensemble de Variables.\\
 - Effacer l'ensemble d'Outcomes générées.

\subsubsection{Preference}

\textbf{Attributs}\\
 - Une chaine de caractères contenant la valeur la plus préférée.\\
 - Une chaine de caractères contenant la valeur la moins préférée.\\
 - Une chaine de caractères contenant la condition.\\
 . La condition sera égale à une chaîne vide ( "" ) si la préférence n'est pas conditionnelle.\\

\textbf{Méthodes}\\
 - Récupérer les deux valeurs.\\
 - Récupérer la condition.
 
\subsubsection{Constraint}
\textbf{Attributs}\\
 - Une collection d'Outcomes (Droit).\\
 - Une collection d'Outcomes (Gauche).\\

\textbf{Méthodes}\\
 - Récupérer l'ensemble droit.\\
 - Récupérer l'ensemble gauche.\\
 - Vérifier si une Outcome est dans l'ensemble droit.\\
 - Vérifier si une Outcome est dans l'ensemble gauche.\\
 - Effacer une Outcome d'un des ensembles.

\newpage
\subsection{Diagramme UML}
Voici le diagramme UML illustrant notre analyse : \\

\includegraphics[height=19cm]{UML2.png}

\subsection{Reflexion sur les améliorations}
\subsubsection{Gérer les collections}
Nous avons besoin d'utiliser des collections d'objets. Certaines pourront être très importantes (ensemble Omega, contraintes), nous avons donc besoin de les traiter le mieux possible.\\
Nous avons tout d'abord pensé à utiliser des tableaux de pointeurs, mais certaines opérations semblent plutôt coûteuses en temps et en mémoire.\\
Nous avons donc cherché du côté de la bibliothèque STL (puisque nous utiliserons C++) qui propose trois conteneurs de séquence : \\
\begin{itemize}
\item La liste : elle permet les insertions/suppressions rapides n'importe où dans le conteneur, mais on ne peut pas accéder directement à un élément. Elle prend un peu plus de place qu'un vecteur.\\
\item Le vecteur : il se comporte comme un tableau. Les insertions/suppressions internes sont linéaires à la taille du tableau.\\
\item Le deque : il permet d'accéder rapidement à un élément et les insertions/suppressions sont rapides au début et à la fin du conteneur. L'insertion au milieu est linéaire.\\
\end{itemize}
Voyons ensuite les traitements que nous allons devoir faire sur Omega et sur les contraintes : \\
 - Générer la collection : ajout d'Outcome à la fin (ou au debut).\\
 - Parcourir tous les éléments.\\
 - Supprimer les éléments de Omega et des contraintes durant les algorithmes : suppression en milieu de conteneur.\\
Il semblerait donc que nous n'ayons pas besoin d'accéder à un élément précis, et que la suppression en milieu de conteneur se fera très fréquement durant les algorithmes. \\
List semble le plus approprié pour ce genre d'objets, qui vont contenir de grandes collections d'Outcomes.\\
Les autres conteneurs étant très petits comparés à ceux-ci (les Variables contiennent quelques valeurs, Omega contient le nombre de variables, les Outcomes une instanciation ...), et l'accès direct à un de ces éléments étant nécessaire dans la plupart des cas, le vector sera préférable.

\subsubsection{Génération de l'espace d'alternatives combinatoire en extension}
Nous avons réfléchi à la meilleure solution pour générer toutes les Outcomes. Nous avons trouvé deux façons de procéder : \\

\textbf{Arborescente}\\
La première solution à laquelle nous avions pensé générait les Outcomes de façon "arborescente". En voici le principe : \\
 - On prend une Outcome dans Omega et on l'associe à une Variable : on génère alors autant de nouvelles Outcomes qu'il y a de valeurs dans le domaine de la Variable, chacune de ces Outcomes possédant les valeurs de celle de départ plus une des valeurs du domaine.\\
On efface l'Outcome de départ de Omega et on ajoute les nouvelles.\\
 - On répète cette opération pour chaque Variable de l'ensemble sur lequel Oméga est fondé.\\
\\
\textit{Exemple : }\\
v1 = \{bleu, rouge\} ; v2 = \{faible, fort\} ; v3 = \{12, 16\} \\
1) Oméga est vide. La première variable, v1, génère donc deux Outcomes : \{bleu\} et \{rouge\} \\
2) On associe chaque Outcomes de Oméga, ici deux, avec la variable v2 : \\
\{bleu\} donne \{bleu, faible\} et \{bleu, fort\} \\
\{rouge\} donne \{rouge, faible\} et \{rouge, fort\} \\
On efface \{bleu\} et \{rouge\} de Omega et on les remplace par les quatre Outcomes obtenues ci-dessus.\\
3) On associe chaque Outcomes de Oméga, ici 4, avec la variable v3 :\\
\{bleu, faible\} donne \{bleu, faible, 12\} et \{bleu, faible, 14\} \\
\{bleu, fort\} donne \{bleu, fort, 12\} et \{bleu, fort, 14\} \\
\{rouge, faible\} donne \{rouge, faible, 12\} et \{rouge, faible, 14\} \\
\{rouge, fort\} donne \{rouge, fort, 12\} et \{rouge, fort, 14\} \\
De la même façon, on remplace les anciennes Outcomes par celles-ci. L'ensemble est généré.\\

\textbf{Linéaire}\\
Cette fois-ci, au lieu de générer Omega "petit à petit", nous allons directement générer toutes les Outcomes.\\
Pour ceci on crée un "compteur" : il possède autant de chiffres que Oméga possède de variables, chacun de ces chiffres pouvant aller de 0 au nombre de valeurs dans le domaine de la variable qu'il représente, moins un. A chaque incrémentation, on obtient une nouvelle combinaison et donc une nouvelle instanciation : on crée alors une nouvelle Outcome que l'on place dans Oméga.\\
\\
\textit{Exemple : }\\
v1 = \{bleu, rouge\} ; v2 = \{faible, fort\} ; v3 = \{12, 16\} \\
000 : \{bleu, faible, 12\} \\
001 : \{bleu, faible, 16\}\\
010 : \{bleu, fort, 12\}\\
011 : \{bleu, fort, 16\}\\
... \\
110 : {rouge, fort, 12\}\\
111 : \{rouge, fort, 14\} \\

\textbf{Comparaison}\\
Après implémentation, nous avons fait un test sur un grand nombre d'Outcomes : 8 variables de chacune 5 valeurs, c'est-à-dire 390 625 Outcomes. Nous avons calculé le temps approximatif pour chaque génération et répété ceci 10 fois, et ce pour les deux fonctions : \\
\\
\includegraphics[height=9cm]{testomega1.png}
\\ \\
\includegraphics[height=9cm]{testomega2.png}
\\ \\
La génération "Arborescente" prend donc moins de temps que la "Linéaire". A l'échelle à laquelle nous allons travailler, la différence entre ces deux fonctions ne se voit quasiment pas, mais nous allons tout de même utiliser la première.





	




%-------------------------------------------------------------------------------------------------
%-------------------------------------------------------------------------------------------------
%                         DESCRIPTION ET ECRITURE DES ALGORITHMES 
%-------------------------------------------------------------------------------------------------
%-------------------------------------------------------------------------------------------------
\newpage
\section{Algorithmes}



%------------------------------ STRONG, MINIMUM DE SPECIFICITE -----------------------------------

	\subsection{Strong, minimum de spécificité}

		\subsubsection{Descriptif}

On cherche parmi les contraintes, les solutions qui ne falsifient aucune préférence : 
c’est-à-dire les solutions que l’on ne trouve dans aucune des parties droites. On dit que ces solutions ne sont 
dominées par aucune autre.\\
On les place dans un premier ensemble. On enlève ensuite ces solutions de la partie gauche de chaque contrainte 
ainsi que de l’ensemble des solutions possibles. Les contraintes qui ont une partie gauche vide sont supprimées.\\
On recommence cette opération jusqu’à ce que l’ensemble des solutions possibles soit vide, ou que l'on obtient un ensemble vide.\\
On renvoie à la fin les ensembles obtenus dans leur ordre d’apparition.


		\subsubsection{Algorithme}

\begin{algorithm}[H]
\SetVline
\KwData{$\Omega$ : l'ensemble des solutions, ps : un jeu de préférence.}
\KwResult{Renvoie le préordre pr.}
\BlankLine

\emph{Variables :} i, j : entiers, C : vecteur de contraintes, E : vecteur d'Outcome,\\
\hspace{1.9cm}pr : vecteur de E.
\BlankLine

\Begin
{
	Générer $\Omega$ \;
	\BlankLine
	Créer C \;
	\For{$i\leftarrow 0$ \KwTo taille(C)}
	{
		C $\leftarrow$ Contrainte( o, ps(i) ) \;
	}
	\BlankLine
	\While{$\Omega$ != $\emptyset$}
	{
		Créer E \;
		\For{$i\leftarrow 0$ \KwTo taille(C)}
		{
			Soit $\omega$ tel que $\omega \notin$ Droite(C[i]), alors E $\leftarrow$ E $\cup$ $\omega$ \;
		}
		\If{E == $\emptyset$}
		{
			Retourner le préordre pr \;
		}
		\For{$i\leftarrow 0$ \KwTo taille(E)}
		{
			\If{E[i] $\in \Omega$}
			{
				$\Omega \leftarrow \Omega$ - E[i] \;
			}
			\For{$j\leftarrow 0$ \KwTo taille(C)}
			{
				\If{E[i] $\in$ Gauche(C[j])}
				{
					Gauche(C[j]) $\leftarrow$ Gauche(C[j]) - E[i] \; 
				}
			}
		}
		\For{$i\leftarrow 0$ \KwTo taille(C)}
		{
			\If{Gauche(C[i]) == $\emptyset$}
			{
				C $\leftarrow$ C - C[i] \;
			}
		}
		pr $\leftarrow$ pr $\cup$ E \;
	}
	\BlankLine
	Retourner le préordre pr \;
}
\end{algorithm}
%-------------------------------------------------------------------------------------------------





%------------------------------ STRONG, MAXIMUM DE SPECIFICITE -----------------------------------
\newpage
	\subsection{Strong, maximum de spécificité}

		\subsubsection{Descriptif}

Cet algorithme est semblable au précédent, sauf qu’on l’exécute à "l’envers".\\
On cherche parmi les contraintes les solutions qui ne valident aucune préférence, c’est-à-dire celles qui
ne sont dans aucune des parties gauches. Ce sont les solutions qui n’en dominent aucune autre.\\
On les place dans un ensemble et on les retire de la partie droite de chaque contrainte, ainsi que de
l’ensemble des solutions possibles.\\
On recommence cette opération jusqu’à ce que l’ensemble des solutions possibles soit vide, ou que l'on obtienne un ensemble vide.\\
On renvoie à la fin les ensembles obtenus dans l’ordre inverse de leur apparition.



		\subsubsection{Algorithme}

\begin{algorithm}[H]
\SetVline
\KwData{$\Omega$ : l'ensemble des solutions, ps : un jeu de préférence.}
\KwResult{Renvoie le préordre pr.}
\BlankLine

\emph{Variables :} i, j : entiers, C : vecteur de contraintes, E : vecteur d'Outcome,\\
\hspace{1.9cm}pr : vecteur de E.
\BlankLine

\Begin
{
\BlankLine
	Générer $\Omega$ \;
	\BlankLine
	Créer C \;
	\For{$i\leftarrow 0$ \KwTo taille(C)}
	{
		C $\leftarrow$ Contrainte( o, ps(i) ) \;
	}
	\BlankLine
	\While{$\Omega$ != $\emptyset$}
	{
		Créer E \;
		\For{$i\leftarrow 0$ \KwTo taille(C)}
		{
			Soit $\omega$ tel que $\omega \notin$ Gauche(C[i]), alors E $\leftarrow$ E $\cup$ $\omega$ \;
		}
		\BlankLine
		\If{E == $\emptyset$}
		{
			Retourner le préordre pr dans l'ordre inverse \;
		}
		\BlankLine
		\For{$i\leftarrow 0$ \KwTo taille(E)}
		{
			\If{E[i] $\in \Omega$}
			{
				$\Omega \leftarrow \Omega$ - E[i] \;
			}
			\BlankLine
			\For{$j\leftarrow 0$ \KwTo taille(C)}
			{
				\If{E[i] $\in$ Droite(C[j])}
				{
					Droite(C[j]) $\leftarrow$ Droite(C[j]) - E[i] \; 
				}
			}
		}
		\BlankLine
		\For{$i\leftarrow 0$ \KwTo taille(C)}
		{
			\If{Droite(C[i]) == $\emptyset$}
			{
				C $\leftarrow$ C - C[i] \;
			}
		}
		pr $\leftarrow$ pr $\cup$ E \;
	}
	\BlankLine
	Retourner le préordre pr dans l'ordre inverse \;
\BlankLine
}
\end{algorithm}
%%-----------------------------------------------------------------------------------------------





%------------------ CETERIS PARIBUS, MINIMUM ET MAXIMUM DE SPECIFICITE ---------------------------
\newpage
	\subsection{Ceteris Paribus, minimum et maximum de spécificité}

		\subsubsection{Descriptif}
Les algoritmes Ceteris Paribus fonctionnent sur le même schéma que les algorithmes Strong.\\
La différence se trouve dans la modification des contraintes après avoir construit un ensemble.\\
On dit qu’une solution est préférée à une autre selon la sémantique Ceteris Paribus si :
\begin{itemize}
	\item elle contient la valeur "la plus préférée" de la préférence comparative,
	\item en dehors des variables précisés dans la préférence comparative, toutes les autres valeurs des variables des deux solutions sont les mêmes.
\end{itemize}
\bigskip
La modification se fait alors comme suit :
\begin{description}
	\item[Minimum de spécificité :] Soit un élément w de l’ensemble obtenu, présent dans la partie gauche
d’une contrainte. Soit w’ tel que w est préféré à w’ selon Ceteris Paribus. On retire w de la partie
gauche et w’ de la partie droite de la contrainte.
	\item[Maximum de spécificité :] Soit un élément w de l’ensemble obtenu, présent dans la partie droite d’une contrainte. Soit w’ tel que w est préféré à w’ selon Ceteris Paribus. On retire w de la partie droite et
w’ de la partie gauche de la contrainte.
\end{description}



		\subsubsection{Algorithme : Ceteris Paribus, minimum de spécificité}

\begin{algorithm}[H]
\SetVline
\KwData{$\Omega$ : l'ensemble des solutions, ps : un jeu de préférence.}
\KwResult{Renvoie le préordre pr.}
\BlankLine

\emph{Variables :} i, j : entiers, C : vecteur de contraintes, E : vecteur d'Outcome,\\
\hspace{1.9cm}pr : vecteur de E.
\BlankLine

\Begin
{
\BlankLine
	Générer $\Omega$ \;
	\BlankLine
	Créer C \;
	\For{$i\leftarrow 0$ \KwTo taille(C)}
	{
		C $\leftarrow$ Contrainte( o, ps(i) ) \;
	}
	\BlankLine
	\While{$\Omega$ != $\emptyset$}
	{
		Créer E \;
		\For{$i\leftarrow 0$ \KwTo taille(C)}
		{
			Soit $\omega$ tel que $\omega \notin$ Droite(C[i]), alors E $\leftarrow$ E $\cup$ $\omega$ \;
		}
		\BlankLine
		\If{E == $\emptyset$}
		{
			Retourner le préordre pr \;
		}
		\BlankLine
		\For{$i\leftarrow 0$ \KwTo taille(E)}
		{
			\If{E[i] $\in \Omega$}
			{
				$\Omega \leftarrow \Omega$ - E[i] \;
			}
			\BlankLine
			\For{$j\leftarrow 0$ \KwTo taille(C)}
			{
				\If{E[i] $\in$ Gauche(C[j])}
				{
					Gauche(C[j]) $\leftarrow$ Gauche(C[j]) - E[i] \; 
				}
			}
			\BlankLine
			\For{$j\leftarrow 0$ \KwTo taille(C)}	
			{
				Soit $\omega_{Droite} \in$ Droite(C[j]) privée de S$_{j}$(la préférence la moins préférée) \;
				Soit $\omega_{E} \in$ E privée de S$_{j}$(la préférence la plus préférée) \;
				\If{$\omega_{Droite}$ == $\omega_{E}$}
				{ 
					Droite(C[j]) $\leftarrow$ Droite(C[j]) - $\omega_{Droite}$ ;
				}
			}
		}
		\BlankLine
		\For{$i\leftarrow 0$ \KwTo taille(C)}
		{
			\If{Gauche(C[i]) == $\emptyset$}
			{
				C $\leftarrow$ C - C[i] \;
			}
		}
		pr $\leftarrow$ pr $\cup$ E \;
	}
	\BlankLine
	Retourner le préordre pr \;
\BlankLine
}
\end{algorithm}

%__________________________________________________________________________________________________

		\subsubsection{Algorithme : Ceteris Paribus, maximum de spécificité}




\begin{algorithm}[H]
\SetVline
\KwData{$\Omega$ : l'ensemble des solutions, ps : un jeu de préférence.}
\KwResult{Renvoie le préordre pr.}
\BlankLine

\emph{Variables :} i, j : entiers, C : vecteur de contraintes, E : vecteur d'Outcome,\\
\hspace{1.9cm}pr : vecteur de E.
\BlankLine

\Begin
{
\BlankLine
	Générer $\Omega$ \;
	\BlankLine
	Créer C \;
	\For{$i\leftarrow 0$ \KwTo taille(C)}
	{
		C $\leftarrow$ Contrainte( o, ps(i) ) \;
	}
	\BlankLine
	\While{$\Omega$ != $\emptyset$}
	{
		Créer E \;
		\For{$i\leftarrow 0$ \KwTo taille(C)}
		{
			Soit $\omega$ tel que $\omega \notin$ Gauche(C[i]), alors E $\leftarrow$ E $\cup$ $\omega$ \;
		}
		\BlankLine
		\If{E == $\emptyset$}
		{
			Retourner le préordre pr dans l'ordre inverse \;
		}
		\BlankLine
		\For{$i\leftarrow 0$ \KwTo taille(E)}
		{
			\If{E[i] $\in \Omega$}
			{
				$\Omega \leftarrow \Omega$ - E[i] \;
			}
			\BlankLine
			\For{$j\leftarrow 0$ \KwTo taille(C)}
			{
				\If{E[i] $\in$ Droite(C[j])}
				{
					Droite(C[j]) $\leftarrow$ Droite(C[j]) - E[i] \; 
				}
			}
			\BlankLine
			\For{$j\leftarrow 0$ \KwTo taille(C)}	
			{
				Soit $\omega_{Gauche} \in$ Gauche(C[j]) privée de S$_{j}$(la préférence la plus préférée) \;
				Soit $\omega_{E} \in$ E privée de S$_{j}$(la préférence la moins préférée) \;
				\If{$\omega_{Gauche}$ == $\omega_{E}$}
				{ 
					Gauche(C[j]) $\leftarrow$ Gauche(C[j]) - $\omega_{Gauche}$ ;
				}
			}
		}
		\BlankLine
		\For{$i\leftarrow 0$ \KwTo taille(C)}
		{
			\If{Droite(C[i]) == $\emptyset$}
			{
				C $\leftarrow$ C - C[i] \;
			}
		}
		pr $\leftarrow$ pr $\cup$ E \;
	}
	\BlankLine
	Retourner le préordre pr dans l'ordre inverse \;
\BlankLine
}
\end{algorithm}
%%------------------------------------------------------------------------------------------------





%-------------------------------------- OPTIMISTE ------------------------------------------------
\newpage
	\subsection{Optimiste}

		\subsubsection{Descriptif}
On cherche les solutions qui n’apparaissent dans aucune partie droite de chaque contrainte, c’est-
à-dire les solutions qui ne falsifient aucune préférence, et on les place dans un ensemble.\\
On retire ensuite ces solutions de l’ensemble des solutions possibles. Enfin, si la partie gauche d’une
contrainte contient au moins un élément de l’ensemble obtenu, on supprime cette contrainte.\\
On recommence enuite l’opération, et ce jusqu’à ce que l’on obtienne un ensemble vide ou qu’il n’y ait
plus de solutions possibles.\\
On renvoie les ensembles obtenus dans leur ordre d’apparition.




		\subsubsection{Algorithme}

\begin{algorithm}[H]
\SetVline
\KwData{$\Omega$ : l'ensemble des solutions, ps : un jeu de préférence.}
\KwResult{Renvoie le préordre pr.}
\BlankLine

\emph{Variables :} i, j : entiers, C : vecteur de contraintes, E : vecteur d'Outcome,\\
\hspace{1.9cm}pr : vecteur de E.
\BlankLine

\Begin
{
\BlankLine
	Générer $\Omega$ \;
	\BlankLine
	Créer C \;
	\For{$i\leftarrow 0$ \KwTo taille(C)}
	{
		C $\leftarrow$ Contrainte( o, ps(i) ) \;
	}
	\BlankLine
	\While{$\Omega$ != $\emptyset$}
	{
		Créer E \;
		\For{$i\leftarrow 0$ \KwTo taille(C)}
		{
			Soit $\omega$ tel que $\omega \notin$ Droite(C[i]), alors E $\leftarrow$ E $\cup$ $\omega$ \;
		}
		\BlankLine
		\If{E == $\emptyset$}
		{
			Retourner le préordre pr \;
		}
		\BlankLine
		\For{$i\leftarrow 0$ \KwTo taille(E)}
		{
			\If{E[i] $\in \Omega$}
			{
				$\Omega \leftarrow \Omega$ - E[i] \;
			}
			\BlankLine
			\For{$j\leftarrow 0$ \KwTo taille(C)}
			{
				\If{E[i] $\in$ Gauche(C[j])}
				{
					C $\leftarrow$ C - Gauche(C[j]) \; 
				}
			}
		}
		pr $\leftarrow$ pr $\cup$ E \;
		\BlankLine
	}
	\BlankLine
	Retourner le préordre pr \;
\BlankLine
}
\end{algorithm}
%%------------------------------------------------------------------------------------------------





%-------------------------------------- PESSIMISTE ------------------------------------------------
\newpage
	\subsection{Pessimiste}

		\subsubsection{Descriptif}
Cet algortihme est semblable au précédent.\\
On place dans un ensemble les solutions qui n’appartiennent à aucune partie gauche de chaque contrainte, 
c’est-à-dire celles qui ne valident aucune préférence.\\
Les éléments de cet ensemble sont retirés de l’ensemble des solutions possibles, et les contraintes qui
possèdent un de ces éléments dans leur partie droite sont supprimées.\\
On répète l’opération tant que Oméga n’est pas vide, ou que l’on n’obtient pas d’ensemble vide.\\
On renvoie ensuite les différents ensembles obtenus dans l’ordre inverse de leur apparition.



		\subsubsection{Algorithme}

\begin{algorithm}[H]
\SetVline
\KwData{$\Omega$ : l'ensemble des solutions, ps : un jeu de préférence.}
\KwResult{Renvoie le préordre pr.}
\BlankLine

\emph{Variables :} i, j : entiers, C : vecteur de contraintes, E : vecteur d'Outcome,\\
\hspace{1.9cm}pr : vecteur de E.
\BlankLine

\Begin
{
\BlankLine
	Générer $\Omega$ \;
	\BlankLine
	Créer C \;
	\For{$i\leftarrow 0$ \KwTo taille(C)}
	{
		C $\leftarrow$ Contrainte( o, ps(i) ) \;
	}
	\BlankLine
	\While{$\Omega$ != $\emptyset$}
	{
		Créer E \;
		\For{$i\leftarrow 0$ \KwTo taille(C)}
		{
			Soit $\omega$ tel que $\omega \notin$ Gauche(C[i]), alors E $\leftarrow$ E $\cup$ $\omega$ \;
		}
		\BlankLine
		\If{E == $\emptyset$}
		{
			Retourner le préordre pr dans l'ordre inverse \;
		}
		\BlankLine
		\For{$i\leftarrow 0$ \KwTo taille(E)}
		{
			\If{E[i] $\in \Omega$}
			{
				$\Omega \leftarrow \Omega$ - E[i] \;
			}
			\BlankLine
			\For{$j\leftarrow 0$ \KwTo taille(C)}
			{
				\If{E[i] $\in$ Droite(C[j])}
				{
					C $\leftarrow$ C - Gauche(C[j]) \; 
				}
			}
		}
		pr $\leftarrow$ pr $\cup$ E \;
		\BlankLine
	}
	\BlankLine
	Retourner le préordre pr dans l'ordre inverse \;
\BlankLine
}
\end{algorithm}



\end{document}

